package leetcode61_70;

import org.junit.Test;

/**
 * @author shhjiang_001
 * @create 2020-06-20 22:14
 */

        /*一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
        机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
        现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

                网格中的障碍物和空位置分别用 1 和 0 来表示。

                说明：m 和 n 的值均不超过 100。

                示例 1:

                输入:
                [
                [0,0,0],
                [0,1,0],
                [0,0,0]
                ]
                输出: 2*/

public class Solution63 {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        if (obstacleGrid[0][0] == 1) return 0;
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] == 1){
                for (int j = i; j < m; j++) {
                    obstacleGrid[j][0] = 0;
                }
                break;
            }else {
                obstacleGrid[i][0] = 1;
            }
        }
        for (int i = 0; i < n; i++) {
            if (obstacleGrid[0][i] == 1 && i != 0){
                for (int j = i; j < m; j++) {
                    obstacleGrid[0][j] = 0;
                }
                break;
            }else {
                obstacleGrid[0][i] = 1;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1){
                    obstacleGrid[i][j] = 0;
                }else {
                    obstacleGrid[i][j] = obstacleGrid[i-1][j]+obstacleGrid[i][j-1];
                }
            }

        }
        return obstacleGrid[m-1][n-1];
    }

    @Test
    public void test() {
        int i = uniquePathsWithObstacles(new int[][]{{0, 0, 0}, {0, 1, 0}, {0, 0, 0}});
        System.out.println(i);
    }
}
